1. Field of the Invention
The present invention relates generally to signal processing and, more particularly, to a method for more efficiently approximating a physical signal representing a linear or locally linearized system.
2. Description of the Related Art
Physical signals or measurements in space and time dimensions are typically represented in digital form as vectors. Constructing a physical model of these physical signals is then typically represented by solving linear systems of equations in matrix form which involve these vectors. The problem is expressed as solving a set of linear equations, given in matrix form as EQU y=Ax. (1)
Here y is a column vector of size m representing a set of known values, A is a known matrix of size mxn, that is, m rows by n columns, and x is a column vector of size n. The vector x represents the solution of the above system.
An alternative expression for the above physical signal is the eigenvalue problem. This problem involves finding the eigenvalues and eigenvectors of a matrix B, expressed in matrix form as EQU Bq.sub.i =.lambda..sub.i q.sub.i. ( 2)
Here B is a square matrix, .lambda..sub.i is the i'th eigenvalue of matrix B and q.sub.i is the associated i'th eigenvector of matrix B.
If the digital data representing the physical signal is voluminous, then the linear system is going to be large. The number of rows m in the matrix, typically representing the number of measurements, will be large. A system for which mn is called overdetermined. If the number of variables representing the physical model describing the physical signal is large, then the linear system is going to be large. The number of columns n in the matrix, typically representing the parameters of the physical model utilized, will be large. A system for which nm is called underdetermined. If both conditions apply, then both the number of rows and columns in the matrix equations are going to be large. In addition, the matrices may be dense or ill-conditioned. All of these conditions make the matrix equations representing the physical model of the signal difficult to solve.
G. Beylkin et al., "Fast Wavelet Transform and Numerical Algorithms I", Communications for Pure and Applied Mathematics, Vol. XLIV, pp. 141-183, 1991, disclose a method for the conversion of dense matrices into sparse matrices using a wavelet transform. However, the size of the matrices is not diminished.
Thus a method for the approximate solution of large, dense linear systems representing the system of linear equations is desired. An approximate solution for large or ill conditioned systems which otherwise defy classical approaches like a singular value decomposition is needed. In particular, a method which can efficiently decrease the size of either the column dimension, the row dimension, or both simultaneously, while still yielding a good approximation to solving the linear system would be useful.